package cn.aylog.singleLinkList;


import java.util.Stack;

/**
 * 数据结构与算法 之
 *  单向链表
 */
public class Main {
    public static void main(String[] args) {
        SingleList list = new SingleList();
        list.add(new HeroNode(1, "宋江"));
        list.add(new HeroNode(3, "鲁智深"));
        list.add(new HeroNode(5, "武松"));
//        list.add(new HeroNode(3, "宋义"));
//        list.add(new HeroNode(4, "林冲"));
        SingleList list2 = new SingleList();
        list2.add(new HeroNode(1, "宋江b"));
        list2.add(new HeroNode(2, "鲁智深b"));
        list2.add(new HeroNode(6, "武松b"));
//        list2.add(new HeroNode(3, "宋义b"));
//        list2.add(new HeroNode(4, "林冲b"));
//        list.list();
//        System.out.println("=========修改后=========");
//        list.updateNode(new HeroNode(3, "黄蓉"));
//        list.delete(5);
//        list.delete(1);
//        System.out.println("链表的有效长度=" + getLength(list.getHead()));
//        System.out.println(getLastIndexOf(list.getHead(), 1));
//        list.list(reverse2(list.getHead()));
//        reverseShow(list.getHead());
        list.list(merge(list.getHead(), list2.getHead()));
    }

    /**
     * 两个有序链表的合并
     */
    public static HeroNode merge(HeroNode head1, HeroNode head2) {
        // 空判
        if(head1.next == null && head2.next == null) {
            return null;
        } else if(head1.next == null) {
            return head2;
        } else if(head2.next == null){
            return head1;
        }
        HeroNode cur2 = head2.next;
        HeroNode cur1 = head1.next;
        HeroNode pre = head2;
        HeroNode temp = null;
        // link1 加到 link2
        while(true) {
            if(cur1 == null || cur2 == null) {
                break;
            }
            if(cur1.no > cur2.no) {
                pre = cur2;
                cur2 = cur2.next;
            } else {
                // cur2.no >= cur1.no
                temp = cur1.next;
                cur1.next = pre.next;
                pre.next = cur1;
                pre = cur1;
                cur1 = temp;
            }
        }
        return  head2;

    }

    /**
     * 单向链表的逆序打印
     */
    public static void reverseShow(HeroNode head) {
        // 判空
        if(head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp = head.next;
        while(true) {
            if(temp == null) {
                break;
            }
            stack.add(temp);
            temp = temp.next;
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 单向链表的反转
     */
    public static HeroNode reverse(HeroNode head) {
        if(head.next == null) {
            return null;
        }
        HeroNode rHead = new HeroNode(0, "");
        HeroNode cur = head.next;
        HeroNode temp = null;
        while (cur != null) {
            temp = cur.next; // 保存旧链表的顺序
            cur.next = rHead.next; // 往新链表的头进行插入
            rHead.next = cur;
            cur = temp; // 旧链表往后移动
        }
        head.next = rHead.next;
        return head;
    }

    /**
     * 递归实现逆序
     */
    public static HeroNode recall(HeroNode preNode, HeroNode curNode, HeroNode head) {
        if(curNode.next == null) {
            // 最后一个
            head.next = curNode;
        } else {
            recall(curNode, curNode.next, head);
        }
        curNode.next = preNode;
        return preNode;
    }

    public static HeroNode reverse2(HeroNode head) {
        if(head.next == null) {
            return null;
        }
        if(head.next.next == null) {
            return head;
        }
        // 最后一个需要将next置为null
        recall(head.next, head.next.next, head).next = null;
        return head;
    }

    /**
     * 获取的链表的倒数第k个元素
     * 1.先获取总长度
     * 2.在获取第 length - k 个元素
     */
    public static HeroNode getLastIndexOf(HeroNode head, int rIndex) {
        // 判空
        if(head.next == null) {
            return null;
        }
        HeroNode cur = head.next;
        // 获取正的指定下标
        int index = getLength(head) - rIndex;
        if(rIndex <= 0 || index < 0) { // 索引为负数,索引越界
            return null;
        }
        while(cur != null) {
            if(index == 0) {
                break;
            }
            index--;
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 获取链表的长度
     */
    public static int getLength(HeroNode head) {
        if(head.next == null) {
            return 0;
        }
        HeroNode temp = head.next;
        int len = 0;
        while(temp != null) {
            len++;
            temp = temp.next;
        }
        return len;
    }
}


class HeroNode{
    int no;
    String name;
    HeroNode next;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

class SingleList {
    private HeroNode head = new HeroNode(0, "");

    public HeroNode getHead() {
        return head;
    }

    /**
     * 将指定的节点添加到链表
     */
    public void add1(HeroNode node) {
        HeroNode temp = head;
        while(true) {
            if(temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 按顺序插入节点
     */
    public void add(HeroNode node) {
        HeroNode curNode = head;        // 当前节点
        HeroNode nextNode = head.next;  // 下一个节点
        boolean flag = false;
        while(true) {
            if(nextNode == null) {
                break;
            }
            // 这里一定有下一个节点
            if(curNode.no == node.no) {
                flag = true;
                break;
            } else if(curNode.no < node.no && node.no < nextNode.no) { // 当前节点的排名在两个节点之间, 插入
                curNode.next = node;
                node.next = nextNode;
                break;
            }
            curNode = nextNode;
            nextNode = nextNode.next;
        }

        if(flag) {
            System.out.println("错误, 不能有相同的排名~");
        } else {
            curNode.next = node;
        }
    }

    /**
     * 节点更新
     * 1.根据no来修改
     */
    public boolean updateNode(HeroNode newNode) {
        if(head.next == null) {
            System.out.println("链表为空~");
            return false;
        }
        boolean flag = false;
        HeroNode temp = head;
        while(true) {
            if(temp.next == null) {
                break;
            }
            if(temp.next.no == newNode.no) {
                newNode.next = temp.next.next;
                temp.next = newNode;
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(!flag) {
            System.out.println("更新失败, 找不到指定节点~");
        }
        return flag;
    }

    /**
     * 节点删除
     * 根据no来删除
     */
    public boolean delete(int no) {
        if(head.next == null) {
            System.out.println("链表为空~");
            return false;
        }
        boolean flag = false;
        HeroNode temp = head;
        while(true) {
            if(temp.next == null) {
                break;
            }
            if(temp.next.no == no) { // 找到待删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag) {
            // 找到要删除的节点
            temp.next = temp.next.next;
        } else {
            // 没有找到要删除的节点
            System.out.println("没有找到要删除的节点");
        }
        return flag;
    }

    /**
     * 遍历展示
     */
    public void list() {
        // 判空
        if(head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        HeroNode temp = head.next;
        while(true) {
            if(temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 遍历展示
     */
    public void list(HeroNode head) {
        // 判空
        if(head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        HeroNode temp = head.next;
        while(true) {
            if(temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}